package LC203;

/**
 * 移除链表元素
 */

class Solution {
    //方法1
    public ListNode removeElements1(ListNode head, int val) {
        ListNode s = new ListNode(666, head);  //创建哨兵节点
        ListNode p1 = s;  //让p1节点从哨兵开始  不用特判head为空的情况
        ListNode p2;  //p2紧跟在p1后面
        while ((p2 = p1.next) != null) {  //循环  如果p2也就是后一个节点为null  则说明链表已经遍历结束了  p2在进入循环时平移
            if (p2.val == val) {  //p2遇到和要移除元素相等的节点
                p1.next = p2.next;  //p1节点链接p2的下一个节点  也就是把p2节点删除
            } else {  //p2节点不是要删除元素所在节点
                p1 = p1.next;  //正常往下移
            }
        }
        return s.next; //从哨兵的下一个节点作为新链表的head
    }

    //方法2
    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) { //如果为空则返回null
            return null;
        }
        ListNode p = head;
        if (p.val == val) {  //我等于val
            return removeElements2(p.next, val);  //我要被删除  直接返回下一个节点
        }else {
            p.next = removeElements2(p.next, val); //我不用被删除  更新我的下一个节点  并且返回我
            return p;
        }
    }
}
